package net.projecteuler.programs.program0003;

import net.projecteuler.programs.TimeLogger;

/**
 * Largest prime factor
 *
 * The prime factors of 13195 are 5, 7, 13 and 29.
 *
 * What is the largest prime factor of the number 600851475143 ?
 *
 * Created by zhaojjd on 2016/3/21.
 */
public class Program0003 {
    
    public static long find(long num, int base){
        long half = num / base;
        for (int i = base; i < half; i++) {
            if (num % i == 0) {
                return find(num / i, i);
            }
        }
        return num;
    }

    public static long find2(long num, int base){
        int factor = 0;
        while(num > 1){
            if(num % base == 0){
                num /= base;
                factor = base;
            }else {
                base++;
            }
        }
        return factor;
    }

    public static void main(String[] args) {
        long num = 600851475143l;
        TimeLogger.tag();
        System.out.println("find(num, 3) = " + find(num, 3));
        TimeLogger.print();
        TimeLogger.tag();
        System.out.println("find2(num, 3) = " + find2(num, 3));
        TimeLogger.print();
    }

}
